import java.util.*;

//48天笔试强训
public class Main extends Method{

    /**
     * Day 1
     * 1.组队竞赛
     * 2.删除公共字符
     * **/
    /*
    * 1.组队竞赛
    * */
    public static void main1(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();//输入正整数n
        long sum = 0;//水平值和
        int[] array = new int[3 * n];//初始化数组的长度
        for (int i = 0; i < array.length; i++) {
            //输入3 * n个整数
            array[i] = input.nextInt();
        }
        //排序
        //Arrays.sort(array);//调用库方法
        //自己实现快排解决
        quickSort(array);
        for (int i = 0; i < n; i++) {
            sum += array[array.length - 2 * (i + 1)];//累加水平值
        }
        //输入
        System.out.println(sum);

        /*
        * 2.删除公共字符 - 方法1
        * */
        //输入两个字符串
        String str1 = input.nextLine();
        String str2 = input.nextLine();
        StringBuilder stringBuilder = new StringBuilder();
        //遍历第一个字符串
        for (int i = 0; i < str1.length(); i++) {
            //取出第一个字符
            char ch = str1.charAt(i);
            //当字符串2中不存在这个字符
            if (!str2.contains(ch +"")) {
                //拼接上不存在的字符
                stringBuilder.append(ch);
            }
        }
        //输出
        System.out.println(stringBuilder.toString());

        /*
         * 2.删除公共字符 - 方法2
         * */
        //输入两个字符串
        String str3 = input.nextLine();
        String str4 = input.nextLine();
        //定义HashMap
        HashMap<Character, Integer> map = new HashMap<>();

    }

    /**
     * Day 2
     * 1.排序子序列
     * 2.倒置字符串
     * **/
    /*
    * 1.排序子序列
    * */
    public static void main2(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();//输入一个正整数
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = input.nextInt();
        }
        /*
        * flag = 1 表示递增
        * flag = -1 表示递减
        * flag - 0 表示不变
        * */
        int flag = 0;
        int count = 1;//段数
        ///如果不从第二个位置开始数组就越界了
        for (int i = 1; i < n; i++) {
            //此时是递增
            if (array[i] > array[i - 1]) {
                if (flag == 0) {
                    flag = 1;
                }
                //此时递减
                if (flag == -1) {
                    flag = 0;
                    count++;//表示增变减，要分段了
                }
            } else if (array[i] < array[i - 1]){ //此时是递减
                if (flag == 0) {
                    flag = -1;
                }
                if (flag == 1) { //减变增
                    flag = 0;
                    count++;
                }
            }
        }
        System.out.println(count);

        /*
         * 2.字符串倒置
         * */
        //输入字符到数组
        String str = input.nextLine();
        char[] arr = str.toCharArray();
        int len = arr.length;//求子符个数
        //1.先倒置整体的字符
        //调用倒置方法
        reverse(arr, 0, len - 1);
        //2.倒置每一部分的单词
        int start = 0;//记录开始位置
        while (start < len) {
            int end = start;//记录start的位置
            while (end < len && arr[end] != ' ') {
                end++;//找完第一个单词停止
            }
            //此时开始倒置一个单词
            //end此时在空格位置。减1就到了一个单词的最右边
            reverse(arr, start, end - 1);
            start = end + 1;//找下一个单词的开始位置
        }
        //将倒置结束的数组放大一个新的数组中输出
        String newArr = new String(arr);
        System.out.println(newArr);
    }

    /**
     * Day 3
     * 1.找出字符串中连续最长的数字串
     * 2.数组中出现次数超过一半的数字
     * **/
    /*
    * 1.找出字符串中连续最长的数字串
    * */
    public static void main3(String[] args) {
        Scanner input = new Scanner(System.in);
        //输入字符串
        String str = input.nextLine();
        //创建两个空的字符串
        String cur = "";
        String end = "";
        int i = 0;
        //遍历字符串
        for (; i < str.length(); i++) {
            char ch = str.charAt(i);//转成字符
            if (ch >= '0' && ch <= '9') { //是数字
                //放到cur中
                cur = cur + ch + "";
            } else {
                //不是数字
                if (cur.length() > end.length()) {
                    end = cur;
                } else {
                    cur = "";//置为空
                }
            }
        }
        //若字符串的最后一个字符是数字串的最后一个字符，就无法交换end 和 cur
        if (i == str.length() && cur.length() > end.length()) {
            end = cur;
        }
        //输入
        System.out.println(end);

        /*
        * 2.数组中出现次数超过一半的数字
        * */
        //输入正整数
        int n = input.nextInt();
        int[] array = new int[n];//初始化数组
        for (int j = 0; j < n; j++) {
            //输入数组元素
            array[j] = input.nextInt();
        }
        //调用方法1 - 找超过数组长度一半的数字
        //System.out.println(moreThanHalfNum(array));

        //调用方法2 - 找超过数组长度一半的数字
        System.out.println(moreThanHalfNums(array));
    }

    /**
     * Day 4
     * 1.计算糖果
     * 2.进制转换
     * **/
    /*
    * 1.计算糖果
    * */
    public static void main4(String[] args) {
        Scanner input = new Scanner(System.in);
        //输入
        int a = input.nextInt();
        int b = input.nextInt();
        int c = input.nextInt();
        int d = input.nextInt();
        int A  = (a + c) / 2;
        int C = (d - b) / 2;
        int B1 = (b + d) / 2;
        int B2 = (c - a) / 2;
        if (B1 != B2) {
            System.out.println("NO");
        } else {
            System.out.println(A + " " + B1 + " " + C);
        }

        /*
         * 2.进制转换
         * */
        int m = input.nextInt();//要转换的数字
        int n = input.nextInt();//进制数
        StringBuffer stringBuffer = new StringBuffer();//方便添加字符串
        String str = "0123456789ABCDEF";//定义一个字符串表来解决进制超过10的情况
        boolean flag = false;//记录这个数是否为负数
        //转换的数是0
        if (m == 0) {
            System.out.println(0);
            return;
        }
        if (m < 0) {
            //转换的数是负数
            m = -m;
            flag = true;
        }
        while (m != 0) {
            stringBuffer.append(str.charAt(m % n));
            m /= n;
        }
        if (flag) {
            stringBuffer.append('-');//如果是负数在最后加上一个负号
        }
        //反转字符串
        stringBuffer.reverse();
        System.out.println(stringBuffer);//输出
    }

    /**
     * Day 5
     * 1.统计回文
     * 2.连续子数组的最大和
     * **/
    /*
    * 1.统计回文
    * */
    public static void main5(String[] args) {
        Scanner input = new Scanner(System.in);
        //输入两个串
        String str1 = input.nextLine();
        String str2 = input.nextLine();
        int count = 0;//计数器
        for (int i = 0; i < str1.length(); i++) {
            //转为可插入的串
            StringBuilder stringBuilder = new StringBuilder(str1);
            //调用方法插入
            stringBuilder.insert(i, str2);
            //调用非法判断是不是回文数
            if (isPalinDromes(stringBuilder.toString())) {
                //是回文
                count++;
            }
        }
        System.out.println(count);

        /*
         * 2.连续子数组的最大和
         * */
        int size = input.nextInt();
        int[] array = new int[size];
        for(int i = 0; i< size;i++) {
            array[i] = input .nextInt();
        }
        int sum = array[0];
        int max = array[0];
        for(int i = 1;i < size;i++) {
            sum = GetMax(sum + array[i], array[i]); //状态方程
            if (sum >= max)
                max = sum;
        }
        System.out.println(max);
    }

    /**
     * Day 6
     * 1.不要2
     * 2.把字符串转为整数
     * **/
    /*
    * 1.不要2
    * */
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        //输入长和宽
        int row = input.nextInt();
        int col = input.nextInt();
        int count = 0;//计数
        //创建二维数组
        int[][] array = new int[row][col];
        //遍历数组
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (array[i][j] != -1) {
                    count++;//个数加1
                    if (i + 2 < row) {
                        array[i + 2][j] = -1;
                    }
                    if (j + 2 < col) {
                        array[i][j + 2] = -1;
                    }
                }
            }
        }
        System.out.println(count);

        /*
         * 2.把字符串转为整数
         * */
        String str = input.nextLine();
        //调用方法
        int ret = StrToInt(str);
        System.out.println(ret);

    }

    /**
     * Day 7
     * 1.Fibonacci数列
     * 2.合法序列括号判断
     * **/
    /*
    * 1.Fibonacci数列
    * */
    public static void main7(String[] arges) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();//输入一个整数
        int f1 = 0;//第一个数
        int f2 = 1;//第二个数
        while (n > f2) {
            int f3 = f1 + f2;//第三个数
            f1 = f2;
            f2 = f3;
        }
        //求n到f1或者f2的最小步数
        int min = Math.min(n - f1, f2 - n);
        System.out.println(min);

        /*
         * 2.合法序列括号判断
         * */
        String A = input.nextLine();//输入括号字符串
        int num = input.nextInt();//输入A括号字符串的长度
        //调用方法
        boolean ret = chKParenthesis(A, num);
        System.out.println(ret);
    }

}
